Search for: All records

Abstract—Shared information is a measure of mutual de- pendence among multiple jointly distributed random variables with finite alphabets. For a Markov chain on a tree with a given joint distribution, we give a new proof of an explicit characterization of shared information. The Markov chain on a tree is shown to possess a global Markov property based on graph separation; this property plays a key role in our proofs. When the underlying joint distribution is not known, we exploit the special form of this characterization to provide a multiarmed bandit algorithm for estimating shared information, and analyze its error performance. 

Consider a finite set of multiple sources, described by a random variable with m components. Only k ≤ m source components are sampled and jointly compressed in order to reconstruct all the m components under an excess distortion criterion. Sampling can be that of a fixed subset A with |A| = k or randomized over all subsets of size k. In the case of random sampling, the sampler may or may not be aware of the m source components. The compression code consists of an encoder whose input is the realization of the sampler and the sampled source components; the decoder input is solely the encoder output. The combined sampling mechanism and rate distortion code are universal in that they must be devised without exact knowledge of the prevailing source probability distribution. In a Bayesian setting, considering coordinated single-shot sampling and compression, our contributions involve achievability results for the cases of fixed-set, source-independent and source-dependent random sampling.